A Game of Thrones tutorial¶
Game of Thrones (GoT) is an American fantasy drama TV series, created by D. Benioff and D.B. Weiss for the American television network HBO. It is the screen adaption of the series of fantasy novels A Song of Ice and Fire, written by George R.R. Martin. The series premiered on HBO in the United States on April 17, 2011, and concluded on May 19, 2019, with 73 episodes broadcast over eight seasons. With its 12 million viewers during season 8 and a plethora of awards---according to Wikipedia, Game of Thrones has attracted record viewership on HBO and has a broad, active, and international fan base.
The intricate world narrated by George R.R. Martin and scripted by Benioff and Weiss has stimulated the curiosity of ranks of scientists, delighted by the opportunity to study complex social phenomena. In this notebook, we delve into the study of GoT relationships to discover what the hypergraphs they generate reveal about the story.
In this notebook, we replicate some of the analysis you can read in our paper at this link!
What we need... installing and loading packages¶
using Pkg
#pkg"add PyCall Conda SimpleHypergraphs Plots GraphPlot ColorSchemes"
Prerequisites for plotting¶
#using Conda, PyCall
#Conda.runconda(`install matplotlib --yes`)
#Conda.runconda(`install networkx --yes`)
#run(`$(PyCall.python) -m pip install hypernetx==1.2.5`)
using SimpleHypergraphs
using Graphs
using Plots
using GraphPlot, ColorSchemes
The data set¶
This study is based on the dataset at the GitHub repository of Jeffrey Lancaster Game of Thrones Datasets and Visualizations. We will thus focus on the GoT TV series.
We studied GoT characters' co-occurrences with different levels of granularity. We modeled the GoT data set building three different types of hypergraphs, each one reporting whether the GoT characters have appeared in the same season, in the same episode, or in the same scene together.
Hypergraph with each season as an edge¶
First, we load a hypergraph studying characters' co-occurences within seasons. Here, the hyperedges are the GoT seasons and the characters who appear in each eason are the nodes.
pth = joinpath(dirname(pathof(SimpleHypergraphs)),"..","tutorials", "basics", "data", "hg_seasons_all.json");
h = SimpleHypergraphs.hg_load(pth; format=JSON_Format(), T=Bool, V=Symbol, E=Symbol);
# how many characters did we see during the overall TV series?
size(h)[1]
577
# how many characters does each season have?
# we can ask this way...
map(he -> println("Season $he has $(length(getvertices(h, he))) characters"), 1:nhe(h));
Season 1 has 125 characters Season 2 has 137 characters Season 3 has 137 characters Season 4 has 152 characters Season 5 has 175 characters Season 6 has 208 characters Season 7 has 75 characters Season 8 has 66 characters
# ... or this way
length.(h.he2v)
8-element Vector{Int64}:
125
137
137
152
175
208
75
66
SimpleHypergraphs integates the Python library HyperNetX to let the user visualize a hypergraph h exploiting an Euler-diagram visualization. For more details, please refer to the library HyperNetX.
pth = joinpath(dirname(pathof(SimpleHypergraphs)),"..","tutorials", "basics", "data", "hg_seasons_min.json");
# Let's visualize (a smaller parte of) the hypergraph we built
# To build this smaller hypergraph, we considered only those characters
# appearing at least in 10 scenes in the whole series
h1 = SimpleHypergraphs.hg_load(pth; format=JSON_Format(), T=Int, V=Symbol, E=Symbol);
map(he ->
println("Season $he has *$(length(getvertices(h1, he)))* characters appearing in at least 10 scenes"),
1:nhe(h));
Season 1 has *69* characters appearing in at least 10 scenes Season 2 has *74* characters appearing in at least 10 scenes Season 3 has *83* characters appearing in at least 10 scenes Season 4 has *83* characters appearing in at least 10 scenes Season 5 has *75* characters appearing in at least 10 scenes Season 6 has *98* characters appearing in at least 10 scenes Season 7 has *56* characters appearing in at least 10 scenes Season 8 has *44* characters appearing in at least 10 scenes
length.(h1.he2v)
8-element Vector{Int64}:
69
74
83
83
75
98
56
44
# viz params: edge labels
edge_labels = Dict{Int, String}(map(x -> x=>"S$x", 1:nhe(h)))
edge_labels_kwargs = Dict{String,Any}("fontsize" => "x-large")
;
SimpleHypergraphs.draw(
h1,
HyperNetX;
no_border = true,
width = 7,
height = 7,
collapse_nodes = true,
with_node_counts = true,
with_node_labels = true,
edge_labels = edge_labels,
edge_labels_kwargs = edge_labels_kwargs
)
# who are the characters appearing in all 8 seasons?
most_important_character_ids = findall(x->x==1, (length.(h.v2he) .== 8))
for id in most_important_character_ids
println(SimpleHypergraphs.get_vertex_meta(h, id))
end
White_Walker Jon_Snow Sansa_Stark Arya_Stark Theon_Greyjoy Cersei_Lannister Jaime_Lannister Tyrion_Lannister Daenerys_Targaryen Jorah_Mormont Drogon Rhaegal Viserion Lord_Varys Samwell_Tarly Bronn
Hypergraph with each scene as an edge¶
# Let's have a closer look of what's happening in season 1
pth = joinpath(dirname(pathof(SimpleHypergraphs)),"..","tutorials", "basics", "data", "hg_season1.json");
hg = SimpleHypergraphs.hg_load(pth; format=JSON_Format(), T=Bool, V=Symbol, E=Symbol);
# how many characters do we have? How many scenes?
"$(nhv(hg)) characters and $(nhe(hg)) scenes"
"125 characters and 286 scenes"
The collaboration structure of Game of Thrones.¶
At this point, we had an overview about how many characters appeared over the whole GoT TV series and which one of them made it till the end.
Let's find out how these characters interacted with each other in season 1. To gather insights within these complex relationships, we run a community detection algorithm on the hypergraph built considering scenes as hyperedges.
Running this algorithm, we expect to find coherent plotlines and, therefore, groups of characters frequently appearing in a scene together.
# Let's assure to have a single connected component
# Otherwise, we pick the largest one
cc = get_connected_components(hg)
2-element Vector{Vector{Int64}}:
[1, 5, 3, 4, 2, 16, 12, 29, 34, 49 … 37, 87, 48, 44, 40, 106, 93, 101, 118, 119]
[99]
remove_vertex!(hg, 99)
cc = get_connected_components(hg)
1-element Vector{Vector{Int64}}:
[1, 5, 3, 4, 2, 16, 12, 29, 34, 49 … 37, 87, 48, 44, 40, 106, 93, 101, 118, 119]
# We used the label propagation (LP) algorithm
cflp = CFLabelPropagationFinder(100,1234)
comms = findcommunities(hg, cflp)
"We found $(length(comms.np)) communities in the hypergraph of the 1st season."
"We found 18 communities in the hypergraph of the 1st season."
length.(comms.np)
18-element Vector{Int64}:
1
1
4
37
1
1
1
18
3
1
16
4
13
7
12
1
1
2
# Who are they?
for c in comms.np
for character in c
println(get_vertex_meta(hg, character))
end
println("-----")
end
White_Walker ----- Ros ----- Shaggydog Nymeria Grey_Wind Lady ----- Loras_Tyrell Renly_Baratheon Grand_Maester_Pycelle Septa_Mordane Old_Nan Mycah Hugh_of_the_Vale Sansa_Stark Hodor Joffrey_Baratheon Gregor_Clegane Jon_Arryn Jory_Cassel Royal_Steward Myrcella_Baratheon Benjen_Stark Rickon_Stark Varly Eddard_Stark Robert_Baratheon Beric_Dondarrion Lancel_Lannister Ilyn_Payne Sandor_Clegane Tommen_Baratheon Cersei_Lannister Joss Janos_Slynt Yoren Petyr_Baelish Arya_Stark Lord_Varys Barristan_Selmy Summer Tomard Jaime_Lannister Meryn_Trant ----- Mhaegen ----- Armeca ----- Tobho_Mott ----- Mirri_Maz_Duur Viserys_Targaryen Irri Drogon Viserion Daenerys_Targaryen Rhaegal Mago Khal_Drogo Wine_Merchant Doreah Qotho Jhiqui Rakharo Illyrio_Mopatis Rhaego Jorah_Mormont Dothraki_Crone ----- Osha Wallen Stiv ----- Three-Eyed_Raven ----- Vardis_Egen Addam_Marbrand Leo_Lefford Chella Robin_Arryn Lannister_Messenger Shae Mord Lysa_Arryn Kevan_Lannister Bronn Timett Marillion Tyrion_Lannister Shagga Tywin_Lannister ----- Walder_Frey Joyeuse_Erenford Stevron_Frey Ryger_Rivers ----- Alliser_Thorne Ghost Rast Jon_Snow Maester_Aemon Jaremy_Rykker Pypar Othell_Yarwyck Jafer_Flowers Othor Jeor_Mormont Samwell_Tarly Grenn ----- Hot_Pie Syrio_Forel Lommy_Greenhands Gendry King's_Landing_Baker Street_Urchin Red_Keep_Stableboy ----- Robb_Stark Jonos_Bracken Theon_Greyjoy Will Lannister_Scout Bran_Stark Greatjon_Umber Catspaw_Assassin Rodrik_Cassel Catelyn_Stark Maester_Luwin Rickard_Karstark ----- Wight_Wildling_Girl ----- Little_Bird ----- Waymar_Royce Gared -----
Some comments¶
Based on the communities above, we can say that the LP algorithm ran on such hypergraph revealed:
The presence of minor communities of characters, appearing only in few scenes of the whole season. It is interesting to note that the algorithm correctly identifies background characters that do heavily not contribute to the main storyline (for now).
- (Syrio_Forel);
- (Waymar_Royce, White_Walker, Gared);
- (Three-Eyed_Raven);
- (Hot_Pie, Red_Keep_Stableboy, Vayon_Poole, Gendry);
- ...
The other communities embody the different sub-plotlines happening in the first season. We can list:
- two communities related to Daenerys_Targaryen and the Dothraki;
- one community related to the events happening in Castle Black and related to Jon Snow;
- one community related to the Houses Arryn and Frey.
The last more significant community contains the majority of the characters appearing in the first season. This result makes sense as all these characters have been forced to stay together at the Red Keep. Thus, they appear in many scenes together.
How good these communities are in terms of modularity?¶
modularity(hg, comms.np)
0.5040026252111678
Find communities by maximizing the value of modularity¶
# Here, we used a CNM-Like algorithm for finding communities.
cnm = CFModularityCNMLike(500)
cnm_comms = findcommunities(hg, cnm)
"We found $(length(cnm_comms.bp)) communities in the hypergraph of the 1st season with a modularity value of $(cnm_comms.bm)."
"We found 14 communities in the hypergraph of the 1st season with a modularity value of 0.44905422798563704."
# How many characters are there in each community?
# size of each community
comms_size = length.(cnm_comms.bp)
# how many community of that size do exist?
values = unique(length.(cnm_comms.bp))
data = Dict([(i, count(x->x==i, comms_size)) for i in values])
Dict{Int64, Int64} with 3 entries:
93 => 1
1 => 12
19 => 1
# Who are they?
for c in cnm_comms.bp
for character in c
println(get_vertex_meta(hg, character))
end
println("-----")
end
White_Walker Renly_Baratheon Grand_Maester_Pycelle Ros Joyeuse_Erenford Addam_Marbrand Chella Hodor Myrcella_Baratheon Jon_Snow Shae Gendry Stevron_Frey Lancel_Lannister Arya_Stark Wight_Wildling_Girl Lord_Varys Barristan_Selmy Wallen Shagga Tywin_Lannister Leo_Lefford Old_Nan Mycah Sansa_Stark Joffrey_Baratheon Gregor_Clegane Ghost Lannister_Messenger Armeca Benjen_Stark Three-Eyed_Raven Rickon_Stark Syrio_Forel Varly Stiv Mord King's_Landing_Baker Street_Urchin Osha Bronn Bran_Stark Cersei_Lannister Othell_Yarwyck Timett Janos_Slynt Yoren Marillion Tyrion_Lannister Jeor_Mormont Catspaw_Assassin Waymar_Royce Hot_Pie Catelyn_Stark Maester_Luwin Jaime_Lannister Grey_Wind Ryger_Rivers Meryn_Trant Vardis_Egen Septa_Mordane Nymeria Robin_Arryn Lady Eddard_Stark Robert_Baratheon Tobho_Mott Kevan_Lannister Sandor_Clegane Greatjon_Umber Petyr_Baelish Othor Samwell_Tarly Summer Rickard_Karstark Red_Keep_Stableboy Loras_Tyrell Hugh_of_the_Vale Robb_Stark Jory_Cassel Gared Royal_Steward Shaggydog Mhaegen Lommy_Greenhands Jonos_Bracken Theon_Greyjoy Will Lysa_Arryn Ilyn_Payne Tommen_Baratheon Walder_Frey Rodrik_Cassel ----- Rast ----- Pypar ----- Jon_Arryn ----- Maester_Aemon ----- Beric_Dondarrion ----- Khal_Drogo Wine_Merchant Mirri_Maz_Duur Doreah Viserys_Targaryen Qotho Jhiqui Little_Bird Irri Rakharo Drogon Viserion Daenerys_Targaryen Rhaego Illyrio_Mopatis Rhaegal Jorah_Mormont Dothraki_Crone Mago ----- Alliser_Thorne ----- Jafer_Flowers ----- Tomard ----- Grenn ----- Jaremy_Rykker ----- Lannister_Scout ----- Joss -----
Let's visualize these communities¶
We will visualize the obtained communities through a two-section representation of the hypergraph.
# As a TwoSectionView can be instantiated only for hypergraphs with non-overlapping edges,
# here we will use Graphs.jl directly.
m = get_twosection_adjacency_mx(hg;replace_weights=1)
t = Graph(m)
{124, 886} undirected simple Int64 graph
Just a few viz params¶
my_colors = vcat(ColorSchemes.rainbow[range(1, stop=length(ColorSchemes.rainbow), step=2)], ColorSchemes.rainbow[2]);
function get_color(i, comms, colors)
for j in 1:length(comms)
if i in comms[j]
return colors[j % length(colors) + 1]
end
end
return "black"
end;
degrees = [Graphs.degree(t, v) for v in Graphs.vertices(t)];
dsize = fill(1.3, 124)
dsize += degrees/maximum(degrees);
# evaluate comms labels
function get_labels(comms)
labels = fill("", 124)
index = 1
for c in comms
labels[first(c)] = "C$(index)"
index += 1
end
labels
end
labels = get_labels(comms.np)
cnm_labels = get_labels(cnm_comms.bp);
Communities from Label Propagation¶
gplot(
t,
nodesize = dsize,
nodelabel = labels,
nodelabeldist=2.5,
#nodelabelsize=size,
nodefillc=get_color.(1:Graphs.nv(t), Ref(comms.np), Ref(reverse(my_colors)))
)
Communities from CNM-like¶
gplot(
t,
nodesize = dsize,
nodelabel = cnm_labels,
nodelabeldist = 5.5,
nodelabelsize = dsize,
nodefillc = get_color.(1:Graphs.nv(t), Ref(cnm_comms.bp), Ref(my_colors))
)
Which are the most important characters?¶
Identifying truly important and influential characters in a vast narrative like GoT may not be a trivial task, as it depends on the considered level of granularity. In these cases, the main character(s) in each plotline is referred with the term fractal protagonist(s), to indicate that the answer to "who is the protagonist" depends on the specific plotline.
Degree centrality¶
Who are the characters that apper in the majority of the scenes?
degrees = Dict{Int, Int}()
for v=1:nhv(hg)
degrees[v] = length(gethyperedges(hg, v))
end
sorted_degrees = sort(collect(degrees), by=x->x[2], rev=true);
# Let's plot these data
characters = Array{String, 1}()
degrees = Array{Int, 1}()
max_c = 0
# we will visualize only characters appearing in at least 15 scenes
for c in sorted_degrees
max_c = max_c > 15 ? break : max_c + 1
push!(characters, string(get_vertex_meta(hg, c.first)))
push!(degrees, c.second)
end
degrees
16-element Vector{Int64}:
70
44
41
38
36
32
29
26
26
24
24
22
22
22
21
18
pos = collect(1:length(characters))
bar(degrees, orientation=:h, yticks=(pos, characters), yflip=false, bar_spacing=2.5,ylim=(0, length(pos)+1),label=nothing)
# Set plot attributes
title!("Season 1")
ylabel!("Characters")
Betweenness centrality¶
We investigated the importance of the characters also evaluating the betweenness centrality (BC) metric of hypergraph nodes. BC measures the centrality of a node by computing the number of times that a node acts as a bridge between the other two nodes, considering the shortest paths between them.
Here, we used the concept of s-beetwennes-centrality. Check out the paper for more detail about this metric.
# Here we evaluate betweennes value considering 1-paths, 2-paths, and 3-paths.
betweeness = Dict{Int, Dict{Symbol, Float64}}()
for s=1:3
A = SimpleHypergraphs.adjacency_matrix(hg; s=s)
G = Graphs.SimpleGraph(A)
bc = Graphs.betweenness_centrality(G)
for v=1:nhv(hg)
push!(
get!(betweeness, s, Dict{Symbol, Int}()),
get_vertex_meta(hg, v) => bc[v]
)
end
end
sorted_betweeness = Dict{Int, Any}()
for s=1:3
d = get!(betweeness, s, Dict{Symbol, Int}())
d_sorted = sort(collect(d), by=x->x[2], rev=true)
push!(
sorted_betweeness,
s => d_sorted
)
end
sorted_betweeness
Dict{Int64, Any} with 3 entries:
2 => [:Tyrion_Lannister=>0.0842826, :Jon_Snow=>0.070162, :Eddard_Stark=>0.054…
3 => [:Jon_Snow=>0.056747, :Eddard_Stark=>0.0513413, :Tyrion_Lannister=>0.048…
1 => [:Arya_Stark=>0.271413, :Illyrio_Mopatis=>0.251899, :Tyrion_Lannister=>0…
# Getting top 10 characters for each s-value
#character => (HG_degree, G_degree)
data = Dict{Symbol, Array{Float64, 1}}()
for s=1:3
higher_degree_characters = sorted_betweeness[s][1:10]
for elem in higher_degree_characters
if !haskey(data, elem.first)
if s==1
push!(
get!(data, elem.first, Array{Float64, 1}()),
elem.second,
betweeness[2][elem.first],
betweeness[3][elem.first]
)
elseif s==2
push!(
get!(data, elem.first, Array{Float64, 1}()),
betweeness[1][elem.first],
elem.second,
betweeness[3][elem.first]
)
else
push!(
get!(data, elem.first, Array{Float64, 1}()),
betweeness[1][elem.first],
betweeness[2][elem.first],
elem.second
)
end
end
end
end
#by highest betweenes degree in the graph, s=1
sorted_data = sort(collect(data), by=x->x[2][1], rev=true)
13-element Vector{Pair{Symbol, Vector{Float64}}}:
:Arya_Stark => [0.27141303430561975, 0.020811742624320874, 0.025567689757446024]
:Illyrio_Mopatis => [0.25189924030387845, 0.0, 0.0]
:Tyrion_Lannister => [0.15323433877389522, 0.08428255933571452, 0.048736052575128745]
:Eddard_Stark => [0.11451260512166041, 0.05462031924487055, 0.051341324021137794]
:Catelyn_Stark => [0.11139671344052993, 0.029487862630240228, 0.033451404486765125]
:Jon_Snow => [0.11122931698056152, 0.07016200324650089, 0.05674696356665995]
:Will => [0.06384113021458084, 0.03825136612021858, 0.0]
:Lord_Varys => [0.06377540542298163, 0.0009193736202932523, 0.001578733585930707]
:Rodrik_Cassel => [0.05228209175473733, 0.023788449409135447, 0.017966399768193867]
:Bran_Stark => [0.042489406954219586, 0.0441890894890005, 0.029071370024299194]
:Theon_Greyjoy => [0.038163554220999756, 0.030162976584305612, 0.023194820979115627]
:Robert_Baratheon => [0.01766998385978779, 0.014594012937620571, 0.014715908661845302]
:Sansa_Stark => [0.015381909177319377, 0.020828998970610812, 0.012916363931724326]
import StatsPlots
labels = Array{String, 1}()
s1 = Array{Float64, 1}()
s2 = Array{Float64, 1}()
s3 = Array{Float64, 1}()
for elem in sorted_data
push!(labels, string(elem.first))
push!(s1, elem.second[1])
push!(s2, elem.second[2])
push!(s3, elem.second[3])
end
group_pos = collect(1:length(labels))# the x locations for the groups
width = 0.3 # the width of the bars
StatsPlots.groupedbar(group_pos,
[s1 s2 s3],
xlabel="Groups",
ylabel="Betweenness Centrality Score",
xticks=(group_pos, labels),
label=["1-path" "2-path" "3-path"],
bar_width=0.9,
legend=:topright,
rotation=65)
title!("Season 8")
Some comments¶
The plot above, showing the betweenness centrality scores using (1,2,3)-paths, reveals that removing "shallow" relationships can bring to light a completely different insight about the structure of the network we are analyzing. Specifically, in this case, it is worth noting that:
- Illyrio_Mopatis and Lord_Varys appear among the ten most important characters. However, they disappear when using (2,3)-paths, suggesting that these characters did not contribute in an evident way to the plot (but maybe behind the scenes);
- Arya_Stark appear to be the most critical character when considering 1-paths. Nonetheless, her importance decreases when switching to (2,3)-paths.
This example highlight how just using 2-paths, we can grasp how characters really interact in the plot and which are the guys who tie all characters together.